class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        lib = set(bank)
        visited = set()
        visited.add(startGene)
        queue = [(startGene, 0)]
        while queue:
            gene, cnt = queue.pop(0)
            cnt += 1
            for i in range(8):
                # 每次改变当前基因字符串的一位
                for char in "ACGT":
                    # 枚举四个字符改变当前位i作为下一个处理的基因字符串，即使有一个是当前字符串，但是当前的已经加入visited，因此也不会重复处理
                    next_ = gene[:i] + char + gene[i+ 1:]
                    if next_ not in visited and next_ in lib:
                        # next_基因没有处理过且在库里，是一个可转移的节点
                        if next_ == endGene:
                            return cnt
                        visited.add(next_)  # 下一个基因字符串入哈希表，表示已经入队了
                        queue.append((next_, cnt))
        return -1